package dp.prevClass.exer04;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 在一个数字序列中，找到一个最长的非连续子序列，使得这个子序列是不下降（非递减）。
 * 现有序列A={1,2,3,-1,-2,7,9},则A的最长不下降子序列是{1,2,3,7,9}。
 * 如果有多个最长序列，只需选数字顺位靠后的序列从大到小输出。
 *
 * 输入要求：
 * 输入2行；
 * 第一行一个整数n，表示有n个整数的序列要输入，n<1000;
 * 第二行共有n个整数。
 *
 * 输出要求：
 * 输出最长的不下降子序列，只需选数字顺位靠后的序列从大到小输出。
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        // 1. 状态定义：dp[i]表示以i位置结尾的最长不下降子序列的长度
        int[] dp = new int[n];
        // 2. 状态初始化
        Arrays.fill(dp, 1);
        // 3. 状态转移
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] <= arr[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
        // 4. 返回值
        int maxLen = -1;
        int maxLenIndex = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                maxLenIndex = i;
            }
        }
        if (maxLen == 1) {
            System.out.println(arr[maxLenIndex]);
            return;
        }
        int index = maxLenIndex - 1;
        int prev = arr[maxLenIndex];
        int prevIndex = maxLenIndex;
        maxLen--;
        System.out.print(arr[maxLenIndex] + " ");
        while (index >= 0 && maxLen > 0) {
            if (arr[index] <= prev && dp[index] + 1 == dp[prevIndex]) {
                System.out.print(arr[index] + " ");
                maxLen--;
                prev = arr[index];
                prevIndex = index;
            }
            index--;
        }
    }
}
